package 二叉树;
//https://leetcode-cn.com/problems/balanced-binary-tree/
public class _110_平衡二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    /**
     * 从下往上（最优解）
     * */
    //TODO 不太理解，还要在看
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return depth(root) != -1;
    }
    private int depth(TreeNode root){
        if (root == null ) return 0;
        int left = depth(root.left);
        if (left == -1) return -1;
        int right = depth(root.right);
        if (right == -1) return -1;
        return Math.abs(left-right) <= 1 ? Math.max(left,right) + 1 : -1;
    }


    /**
     * 暴力解法 从上往下计算
     * */
    /*public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        //判断左子树减去右子树的绝对值是否小于等于1 并且 root的左右子树的最大深度相减也要为
        //true ，才会返回true ，否则false;
        return Math.abs(depth(root.left)-depth(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int depth(TreeNode root){
        //求出root节点的最大深度
        if (root == null ) return 0;
        return Math.max(depth(root.left),depth(root.right))+1;
    }*/

}
